package algocasts;

public class P85_minCoinCombination {
    public int coinChange(int[] coins, int sum) {
        int[][] d = new int[coins.length + 1][sum + 1];
        for (int j = 1; j <= sum; j++)
            d[0][j] = Integer.MAX_VALUE;
        for (int i = 1; i <= coins.length; i++) {
            for (int j = 1; j <= sum; j++) {
                int userCurCoin = j >= coins[i - 1] ? d[i][j - coins[i - 1]] : Integer.MAX_VALUE;
                if (userCurCoin != Integer.MAX_VALUE) userCurCoin += 1;
                d[i][j] = Math.min(d[i - 1][j], userCurCoin);
            }
        }
        return d[coins.length][sum] == Integer.MAX_VALUE ? -1 : d[coins.length][sum];
    }

    public int coinChangeOSum(int[] coins, int sum) {
        int[] d = new int[sum + 1];
        for (int j = 1; j <= sum; j++)
            d[j] = Integer.MAX_VALUE;
        for (int i = 1; i <= coins.length; i++) {
            for (int j = coins[i - 1]; j <= sum; j++) {
                if (d[j - coins[i - 1]] != Integer.MAX_VALUE) {
                    d[j] = Math.min(d[j], d[j - coins[i - 1]] + 1);
                }
            }
        }
        return d[sum] == Integer.MAX_VALUE ? -1 : d[sum];
    }
}
